<?php
/**
 * @title 43.字符串相乘 - 大数乘法
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param String $num1
     * @param String $num2
     * @return String
     */
    function multiply($num1, $num2) {
        /**
         * @since 2020-08-13 特殊情况
         */
        if($num1 == "0" OR $num2 == "0"){
            return "0";
        } else {}

        /**
         * @since 2020-08-13 num2长度
         */
        $len2 = strlen($num2);

        /**
         * @since 2020-08-13 num1和各位乘积
         */
        $result = [];

        /**
         * @since 2020-08-13 逐位相乘
         */
        for ($i=$len2-1; $i>=0; $i--){
            $n = $num2[$i];
            if($n != "0"){
                $sum = $num1;
                for ($j=1; $j<$n; $j++){
                    $sum = self::find($sum, $num1);
                }
                $result[] = $sum;
            } else {}

            $num1 = $num1. "0";
        }
        // return $result;

        /**
         * @since 2020-08-13 求和
         */
        $sum = $result[0];
        for($i=1, $len=count($result); $i<count($result); $i++){
            echo "sum={$sum}, result[i]=", $result[$i], PHP_EOL;
            $sum = self::find($sum, $result[$i]);
        }

        /**
         * @return
         */
        return $sum;
    }

    /**
     * @title 大数相加
     * @author start2004
     * @since 2020-08-13 Created
     *
     * @param string $num1
     * @param string $num2
     * @return string
     */
    public function find($num1 = "", $num2 = ""){
        /**
         * @since 2020-08-13 长度
         */
        $len1 = strlen($num1);
        $len2 = strlen($num2);

        /**
         * @since 2020-08-13 保证num1是字符串较长的那个
         */
        if($len1<$len2){
            list($num1, $num2) = [$num2, $num1];
            list($len1, $len2) = [$len2, $len1];
        } else {}

        /**
         * @since 2020-08-13 逐位相加
         */
        $add = 0;
        for ($i=$len1-1, $j=$len2-1; $j>=0; $i--, $j--){
            $n = $num1[$i] + $num2[$j] + $add;
            if($n>=10){
                $add = 1;
                $num1[$i] = $n%10;
            } else {
                $add = 0;
                $num1[$i] = $n;
            }
        }
        // return [$add, $num1];

        /**
         * @since 2020-08-13 高位继续加
         */
        if($add == 1){
            for (; $i>=0; $i--){
                if($num1[$i] == "9"){
                    $num1[$i] = "0";
                } else {
                    $num1[$i] = $num1[$i]+1;
                    break;
                }
            }
            /**
             * @since 2020-08-13 是否最高位也进1
             */
            if($i == -1) {
                $num1 = "1". $num1;
            } else {}
        } else {}

        /**
         * @return
         */
        return $num1;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.21_8.php
 */
$datas = [
    ["9", "9"],
    ["45", "67"],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->multiply($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
